
module fn.adt.graph.Graph


open System.Collections.Generic

open QuickGraph
open QuickGraph.Algorithms.Search



type UndirectedGraph<'TVertex, 'TEdge when 'TVertex :> obj and 'TEdge :> IEdge<'TVertex>> with
    static member fromVE (e : Edge<'TVertex> -> 'TEdge) V E =
        let g = UndirectedGraph<'TVertex, 'TEdge>()
        do
            for v in V do g.AddVertex(v) |> ignore
            for (u,v) in E do g.AddEdge(e(Edge(u,v))) |> ignore
        g

    member this.directAwayFrom (ef : Edge<'TVertex> -> 'TEdge) s =
        let bfs = UndirectedBreadthFirstSearchAlgorithm<'TVertex, 'TEdge>(this)
        let g' = BidirectionalGraph<'TVertex, 'TEdge>()
        let visited = HashSet<'TEdge>()
        let add sender (args : UndirectedEdgeEventArgs<_,_>) =
            if visited.Add(args.Edge) then
                g'.AddEdge(ef(Edge(args.Source, args.Target))) |> ignore
        do
            bfs.SetRootVertex(s)
            bfs.add_InitializeVertex (fun v -> g'.AddVertex(v) |> ignore)
            bfs.add_TreeEdge (fun sender args -> add sender args)
            bfs.add_NonTreeEdge (fun sender args -> add sender args)
            bfs.Compute(s)
        g'


let graph_of_obj<'a when 'a :> obj> (V : 'a list) (E : ('a * 'a) list)  =
    let V', E' = [for v in V -> v:>obj],  [for u,v in E -> u:>obj,v:>obj]
    UndirectedGraph<obj, IEdge<obj>>.fromVE (fun e -> e :> IEdge<obj>) V' E'
